﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
		<title>Recherche A*</title>
		<link rel="stylesheet" type="text/css" href="style.css" />
	</head>
	<body class="twoColFixLtHdr">
    <div id="container">
		<div id="header">Algorithme de recherche de chemin A*</div>

		<div id="menu">
			<ul>
				<li><a href="index.html">Accueil</a></li>
				<li><a href="presentation.html">Présentation</a></li>
				<li><a href="connaissances.html">Connaissances</a></li>
				<li><a href="demarche.html">Démarche</a></li>
				<li><a href="difficultes.html">Difficultés</a></li>
				<li><a href="analyse.html">Analyse</a></li>
				<li><a href="conclusion.html">Conclusion</a></li>
				<li><a href="bibliographie.html">Bibliographie</a></li>
				<li><a href="glossaire.html">Glossaire</a></li>
				<li><a href="telechargement.html">Téléchargement</a></li>
			</ul>
		</div>

		<div id="content"><br />
			<h1>Difficultés</h1><br /><br />
			La première chose à faire dans le cadre de notre recherche était de bien comprendre et assimiler les rouages de l'algorithme de recherche de chemins A*. Nous n'avons pas rencontré de difficulté ici, étant donné que l'algorithme de base n'est  relativement pas très complexe et qu'un article très complet, avec des schémas clairs, étaient présent sur gamedev.net. Je vous réfère donc à cet article pour comprendre l'algorithme, il est dans la section <a href="bibliographie.html">Bibliographie</a>.<br /><br />
            Ensuite, lors de l'implémentation de l'algorithme lui-même, dans sa forme la plus simple, nous avons éprouvé quelques petites difficultés. Comme vous l'aurez sans doute remarqué, le A* utilise les listes assez fréquemment. Personnellement, je (François Roseberry) n'était pas très habitué d'utiliser de façon aussi complète les listes de la STL, c'est pourquoi il m'a fallu une certaine adaptation (pas très longue tout de même).<br /><br />
            Lors de l'implémentation de notre version du A*, nous n'avions pas explicitement songé au cas où le joueur cliquerait dans une zone ne correspondant pas à aucun des noeuds du graphe. Ayant oublié de prévoir cela dans la version initiale, nous avons dû modifier la binarisation des cartes ainsi que l'éditeur afin de prendre en charge des boîtes de collision, solution que nous avions trouvé pour pallier au problème. Nous avons dû aussi retravailler le code de recherche de chemins, le A* lui-même restant intact, lui permettant plutôt, dans le cas d'un clic pas sur un noeud, de rejoindre le noeud le plus près en évitant les collisions avec les boîtes).
		</div>
		<br class="clearfloat" />
		<div id="footer"><br /><p align="center">Par Benoît Tremblay et François Roseberry</p></div>
    </div>
	</body>
</html>